package com.sise.Tree;

import java.util.LinkedList;

/**
 *     226. 翻转二叉树
 */
public class _226_invertTree {

    /**
     * 递归
     */
    public TreeNode invertTree(TreeNode root) {
        // 递归函数的终止条件，节点为空时就返回
        if(root == null) return null;

        // 递归当前节点的左子树、右子树
        invertTree(root.left);
        invertTree(root.right);
        // 交换左右子节点的位置
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        // 对于这里的递归来讲，返回值没有意义，但由于最后需要返回 头节点，故此这里需要返回 root
        return root;
    }

    /**
     *      使用广度遍历的方式，将遍历到的每个节点的 左右子节点都交换位置
     */
    public TreeNode invertTree2(TreeNode root) {

        // 初步非空判断
        if(root == null) return root;

        // 创建一个队列 LinkedList，把它看成是一个队列，因为接口实现了Queue
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 一开始先把头结点放进去，方便遍历其后续的左右子节点
        queue.add(root);

        // 如果队列不为空
        while(!queue.isEmpty()){
            // 每次从队列中取一个节点，交换其左右子节点
            TreeNode tmp =  queue.poll();
            TreeNode leftTmp = tmp.left;
            tmp.left = tmp.right;
            tmp.right = leftTmp;

            // 如果当前节点的左右子节点不为空，则放入队列等待后续处理
            if(tmp.left != null){
                queue.add(tmp.left);
            }
            if(tmp.right != null){
                queue.add(tmp.right);
            }
        }

        // 处理完原样返回
        return root;
    }
}
